1. Field of Invention
The present invention relates generally to data communication systems. More particularly, the present invention relates to systems and methods for creating a primary path between nodes of a mixed protection network that is protected by an alternate path.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. Furthermore, the types of traffic being carried by the Internet are shifting from lower bandwidth applications towards high bandwidth applications which include voice traffic and video traffic.
To address the demand for data communication services, the use of optical networks, such as a synchronous optical network (SONET), is becoming more prevalent. As will be appreciated by those skilled in the art, a SONET network is an example of a time division multiplexed (TDM) network. TDM networks generally allocate single lines to be used amongst multiple users, or customers of data communication services. The single lines may each be divided into slots of time during which each user has access to the single lines.
A network such as a TDM network is generally designed to ensure that information may be transferred between nodes within the network. Often, within a network, information is transferred between two specified nodes, i.e., a source node which sends information and a destination node which receives information. When information is to be sent between a source node and a destination node, a circuit path between the two nodes must be computed so that leased line services may be provided.
Often, to increase the likelihood that data will be successfully transferred, a circuit path between a source node and a destination node may be protected. A protected circuit path may include protected links, e.g., links with 1+1 protection. A protected circuit path may also include unprotected links, provided that there is a corresponding alternate circuit path associated with the unprotected links. An alternate circuit path effectively serves as a “back up” path to a primary circuit path which includes unprotected links in the event that the primary circuit path fails. For instance, when a primary circuit path suffers either a nodal failure or a failure of a link, data that was to be sent through the primary circuit path may be sent through the alternate circuit path instead. As some protected circuit paths may include both protected path segments and unprotected segments, some protected paths may include “partial” alternate path segments which correspond to the unprotected segments.
Networks which include both protected links and unprotected links are considered to be networks with mixed protection domains. FIG. 1 is a diagrammatic representation of one conventional network with a mixed protection domain. A network 104 includes nodes 108 and links 112 which are arranged to include a unidirectional path switched ring (UPSR) and a bidirectional line switched ring (BLSR). Links 112 may either be protected, as for example through ‘1+1’ protection, or unprotected. Links 112a, 112f, and 112k are protected, while links 112b–e, which are included in a UPSR, may be unprotected. Typically, to route a circuit path from node 108a to node 108j, since network 104 includes overlapping domains, e.g., overlapping unprotected and protected domains, the circuit path includes both protected and unprotected links.
Network 104 may represent a communications network which includes metropolitan networks. By way of example, the UPSR may be a representation of a metropolitan network in one city, and the BLSR may be a representation of a metropolitan network in another city. Link 112f, which is characterized by 1+1 protection, may be a core which allows the UPSR to communicate with the BLSR.
Often, within a communications network that includes metropolitan networks, there may be multiple paths between two nodes. In other words, there may be more than one potential circuit path between a particular source node and a particular destination node. FIG. 2 is a diagrammatic representation of a network which includes multiple paths between two nodes. A network 204 includes a local source node 208a and a local destination node 208d, as well as intermediate nodes 208b, 208c. Nodes 208 are interconnected by links 212, 216. Links 212 are protected links, and links 216 are unprotected links. As nodes 208 are interconnected by both protected links 212 and unprotected links 216, e.g., local source node 208a and node 208b are connected by both protected link 212a and unprotected link 216a, network 204 is a mixed protection domain network with overlapping protections.
Typically, when segment of an overall circuit path is to be routed between local source node 208a and local destination node 208d, the path that is chosen is the shortest path between local source node 208a and local destination node 208d which meets particular requirements, e.g., which is protected if a protected path is desired or unprotected if an unprotected path is desired. As will be appreciated by those skilled in the art, an overall circuit path is often assumed to be the shortest path between a source node and a destination node when the segments which make up the overall path are each the shortest available segment between local source and destination nodes.
If an unprotected path between local source node 208a and local destination node 208d is desired, then either a path which uses links 216a, 216b, or a path which uses links 216d, 216c may be selected. If a protected path between local source node 208a and local destination node 208d is desired, unprotected links 216a, 216b may be chosen to make up a primary path, while unprotected links 216d, 216c may be chosen to make up an alternate path to the primary path. As shown, a protected path between local source node 208a and local destination node 208d is not possible using protected links 212, since link 212b and link 212c are each full and have no available bandwidth. Hence, neither a protected path using links 212d, 212c nor a protected path using links 212a, 212b is possible.
In general, when a path is to be selected, substantially all possible paths between a source node and a destination node are considered. By way of example, if a path between local source node 208a and local destination node 208d is to be routed, then all eight possible paths between local source node 208a and local destination node 208d are considered. That is, a path which includes links 212a, 212b, a path which includes links 212d, 212c, a path which includes links 216a, 216b, a path which includes links 216d, 216c, a path which includes links 212a, 216b, a path which includes links 212b, 216a, a path which includes links 212c, 216d, and a path which includes links 212d, 216c are explored.
Exploring multiple paths often proves to be inefficient, as the time and the cost associated with exploring each path may be significant. Often, the multiple paths may include paths which are characteristically the same. Considering multiple paths that are characteristically similar is particularly inefficient especially when a network which includes the multiple paths is a mixed protection domain network with domains which overlap, as circuit paths within such networks must typically be manually created by a network administrator. That is, conventional path routing algorithms such as shortest path first (SPT) algorithms generally may not be used to automatically create circuits or circuit paths in a network with overlapping domains.
Therefore, what is needed is a system and a method for automatically routing circuit paths in networks with overlapping domains. Specifically, what is needed is an efficient system and method for automatically creating circuit paths in mixed protection domain networks that explores representative potential paths of each available characteristic type.